/**
 * @author 徐楠
 * @date 2021/12/21 17:12
 * @version 1.0
 */

package com.xunan.likou;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class LongestHarmonicSubsequence {

    public static void main(String[] args) {

    }

    //解法1
    public static int findLHS1(int[] nums) {
        int answer = 0;
        for(int i=0;i<nums.length;i++){
            int x = nums[i];
            int greater = 0;
            int less = 0;
            int middle = 0;
            for(int j=i+1;j<nums.length;j++){
                if(nums[j]==x+1) greater++;
                else if(nums[j]==x-1) less++;
                else if(nums[j]==x) middle++;
            }
            int y = Math.max(greater, less);
            if(y>0)
                // + 1表示加自己本身 nums【i】
                answer = Math.max(answer, y + middle + 1);
        }
        return answer;
    }

    //解法2
    public int findLHS2(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int ans=0;
        for(int i=0;i<nums.length;i++){
            int x = nums[i];
            map.put(x, map.getOrDefault(x, 0)+1);
            if(map.containsKey(x-1))
                ans = Math.max(ans, map.get(x)+map.get(x-1));
            if(map.containsKey(x+1))
                ans = Math.max(ans, map.get(x)+map.get(x+1));
        }
        return ans;
    }

    //解法3
    public int findLHS3(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        for(int i=0, j=0;j<nums.length;j++){
            while(i<j && nums[j]-nums[i]>1) i++;
            if(nums[j]-nums[i]==1)
                ans = Math.max(ans, j-i+1);
        }
        return ans;
    }



}
